/**
 * 归并排序
 */
function MergeSort(nums) {
    var temp = nums.copy()

    // 合并nums[left ~ mid]和nums[mid+1 ~ right]
    function merge(left, mid, right) {
        var i = left
        var j = mid + 1
        
        for (var k = left; k <= right; k++) {
            if (i > mid) {
                temp[k] = nums[j]
                j = j + 1
            } else if (j > right) {
                temp[k] = nums[i]
                i = i + 1
            } else if (nums[i] < nums[j]) {
                temp[k] = nums[i]
                i = i + 1
            } else {
                temp[k] = nums[j]
                j = j + 1
            }
        }
        
        for (var k = left; k <= right; ++k) {
            nums[k] = temp[k]
        }
    }
    
    function sort(left, right) {
        if (left >= right) {
            return
        }
        var mid = left + (right - left) / 2
        sort(left, mid);
        sort(mid + 1, right)
        merge(left, mid, right)
    }
    
    sort(0, nums.length() - 1)
}
    
var nums = [3, 2, 1, 5, 4, 6, 9, 7, 8]
MergeSort(nums)
println(nums)
